前言

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
那就開始今天的解題吧~

Question

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 < nums[i], target < 10^4
• All the integers in nums are unique.
• nums is sorted in ascending order.

Think

題目給一個從小到大排的數字list(nums)與一個數字(target)，要找出target這個數位於list中的index，如果都找不到就回傳-1。

基本上就是如題目意思做Binary Search。
首先宣告三個變數，mid、left和right：

• mid = 0
• left = 0
• right = len(nums) - 1

接著，就是對半對半的砍，目前right&left的中心mid：

1. mid = int((left + right) / 2)
2. mid = (left + right) // 2)
3. mid = left + ((right - left) / 2)
   上面三種都可以，第一個是算完如果得到小數，直接轉型成int，相當於無條件捨去小數點後的數；第二個是兩者相加除以2取商；第三種是我後來看到的，有點像是left加offset的感覺。

最後，就是看我們的target比mid大還是小：

1. 如果是target小於mid：代表target在mid左邊，所以我們把right設成mid - 1。
2. 如果是target大於mid：代表target在mid右邊，所以我們把left設成mid + 1。
3. 如果是target等於mid：代表我們找到啦~就直接回傳mid的值

如果整個跑完都沒有就表示，list找不到target這個值，就直接回傳-1。

Code

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int mid = 0;
        int left = 0;
        int right = nums.size() - 1;
        
        while(left <= right){
            mid = floor((left+right)/2);
            
            if(nums[mid] > target){
                right = mid - 1;
            } else if(nums[mid] < target){
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
};

Submission

今天就到這邊啦~
大家明天見